package leetcode;

public class LeetCode33 {

    public static void main(String[] args) {
        LeetCode33 leetCode33 = new LeetCode33();
        System.out.println(leetCode33.search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
    }

    //逻辑地址 物理地址
    public int search(int[] nums, int target) {
        if (nums.length == 0)
            return -1;
        int startIndex, i = 0;
        while (i < nums.length - 1 && nums[i] < nums[i + 1]) {
            i++;
        }
        startIndex = i == nums.length - 1 ? 0 : i + 1;
        int left = 0, right = nums.length - 1, mid, index;
        while (left <= right) {
            mid = (left + right) / 2;
            index = (mid + startIndex) % nums.length;
            if (target == nums[index])
                return index;
            else if (target < nums[index]) {
                right = mid - 1;
            } else
                left = mid + 1;
        }
        return -1;
    }
//------------------------------------------------------------------
}
